#include <iostream>
#include <cstdlib>
#include <vector>

#define BLACK false
#define RED true

template <typename T>
class Node
{
	public:
		T data;
		Node* lc;
		Node* rc;
		Node* parent;
		bool color;
		Node(T _data)
		{
			data = _data;
			color = RED;
			parent = lc = rc = NULL;
		}
};

template <typename T>
class RedBlackTree
{
	public:
		Node<T>* root;
		Node<T>* nil;
		RedBlackTree(T _data);
		void inorder_walk();
		void inorder_walk(Node<T>* _x);
		Node<T>* min(Node<T>* _x);
		Node<T>* max(Node<T>* _x);
		void insert(T _data);
		void Delete(T _data);
		void LeftRotate(Node<T>* _x);
		void RightRotate(Node<T>* _x);
		int transplant(Node<T>* _u, Node<T>* _v);
};

template <typename T>
int RedBlackTree<T>::transplant(Node<T>* _u, Node<T>* _v)
{
    if (_u == nil)
    {
	std::cerr << "Error! Can not transplant to a NULL."<< std::endl;
	std::exit(-1);
    }
    if (_u->parent == nil)
		root = _v;   /// Here can not use _u = _v;
    else if (_u == _u->parent->lc)
		_u->parent->lc = _v;
    else
		_u->parent->rc = _v;
//    if (_v != nil)
    _v->parent = _u->parent;
    return 0;
};

template <typename T>
void RedBlackTree<T>::LeftRotate(Node<T>* _x)
{
	Node<T>* y = _x->rc;
    _x->rc = y->lc;
    if (y->lc != nil)
		y->lc->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
		root = y;
    else if (_x == _x->parent->lc)
		_x->parent->lc = y;
    else
		_x->parent->rc = y;
    y->lc = _x;
    _x->parent = y;
};

template <typename T>
void RedBlackTree<T>::RightRotate(Node<T>* _x)
{
	Node<T>* y = _x->lc;
    _x->lc = y->rc;
    if (y->rc != nil)
		y->rc->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
		root = y;
    else if (_x == _x->parent->lc)
		_x->parent->lc = y;
    else
		_x->parent->rc = y;
    y->rc = _x;
    _x->parent = y;
};

template <typename T>
RedBlackTree<T>::RedBlackTree(T _data)
{
	Node<T>* p = new Node<T>(_data);
	nil = NULL;
	root = p;
	root->color = BLACK;
	root->parent = nil;
	root->lc = nil;
	root->rc = nil;
};

template <typename T>
Node<T>* RedBlackTree<T>::max(Node<T>* _x)
{
    while (_x->rc != nil)
		_x = _x->rc;
    return _x;
};

template <typename T>
Node<T>* RedBlackTree<T>::min(Node<T>* _x)
{
    while (_x->lc != nil)
		_x = _x->lc;
    return _x;
};

template <typename T>
void RedBlackTree<T>::inorder_walk()
{
    Node<T>* p = root;
	if (p != nil)
    {
	inorder_walk(p->lc);
	std::cout << p->data << " " << p->color << "\t";
	inorder_walk(p->rc);
    }
};

template <typename T>
void RedBlackTree<T>::inorder_walk(Node<T>* _x)
{
	if (_x != nil)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << " " << _x->color << "\t";
	inorder_walk(_x->rc);
    }
};

template <typename T>
void RedBlackTree<T>::insert(T _data)
{
    Node<T>* x = new Node<T>(_data);
    Node<T>* y = nil;
    Node<T>* z = root;
    while (z != nil)
    {
		y = z;
		if (x->data  < z->data)
	    	z = z->lc;
		else
	    	z = z->rc;
    }
    x->parent = y;
    if (y == nil)
		root = x;
    else if (x->data < y->data)
		y->lc = x;
    else
		y->rc = x;
	x->lc = nil;
	x->rc = nil;
    if (x->parent->color == BLACK)
    	this->root->color = BLACK;
    while (x->parent != this->nil && x->color == RED)
    {
		if (x->parent->color == BLACK)
			break;
		if (x->parent == x->parent->parent->lc)
		{
	    // y is the uncle of x.
	    	Node<T>* y = x->parent->parent->rc;
	    	if (y == nil)
	    	{
	    		if (x == x->parent->rc)
				{
			    	this->LeftRotate(x->parent);
			    	x = x->lc;
				}
				if (x->parent->parent == root)
	    			root = x->parent;
				this->RightRotate(x->parent->parent);
				x->parent->color = BLACK;
				x->parent->rc->color = RED;
				x = x->parent;
				break;
	    	}
	    // case I:
	    	if (y->color == RED)
	    	{
				x->parent->color = y->color = BLACK;
				if (x->parent->parent == root)
					break;
				else
				{
					x->parent->parent->color = RED;
					x = x->parent->parent;
					if (x->parent->color == BLACK)
		    			break;
				}	
	    	}
	    // y->color == BLACK.
	    	else
	    	{
		// tortuous...
				if (x == x->parent->rc)
				{
		    // case II:
		    		this->LeftRotate(x->parent);
		    		x = x->lc;
				}
		// case III:
				this->RightRotate(x->parent->parent);
				x->parent->color = BLACK;
				x->parent->rc->color = RED;
				x = x->parent;
				break;
	    	}
		}
    	else if (x->parent == x->parent->parent->rc)
		{
	    	Node<T>* y = x->parent->parent->lc;
	    	if (y == nil)
	    	{
	    		if (x == x->parent->lc)
				{
			    	this->RightRotate(x->parent);
			    	x = x->rc;
				}
				if (x->parent->parent == root)
	    			root = x->parent;
				this->LeftRotate(x->parent->parent);
				x->parent->color = BLACK;
				x->parent->lc->color = RED;
				x = x->parent;
				break;
	    	}
	    // case I:
	    	if (y->color == RED)
	    	{
				x->parent->color = y->color = BLACK;
				x->parent->parent->color = RED;
				x = x->parent->parent;
				if (x->parent->color == BLACK)
		    		break;
	    	}
	    	else
	    	{
				if (x == x->parent->lc)
				{
		    // case II:
			    	this->RightRotate(x->parent);
			    	x = x->rc;
				}
		// case III:
				this->LeftRotate(x->parent->parent);
				x->parent->color = BLACK;
				x->parent->lc->color = RED;
				x = x->parent;
				break;
	    	}
		}
    	this->root->color = BLACK;
	}
};

template <typename T>
void RedBlackTree<T>::Delete(T _data)
{
    Node<T>* _x = root;
    while (_x->data != _data)
    {
		if (_data  < _x->data)
	    	_x = _x->lc;
		else
	    	_x = _x->rc;
    }
	Node<T>* y = _x;
    bool original_color_y = y->color;
    Node<T>* x;
    if (_x->lc == this->nil && _x->rc == this->nil)
    {
    	if (_x == _x->parent->lc)
			_x->parent->lc = nil;
		else
			_x->parent->rc = nil;
		x = _x;
	}
    else if (_x->lc == this->nil)
    {
		x = _x->rc;
		this->transplant(_x, _x->rc);
    }
    else if (_x->rc == this->nil)
    {
		x = _x->lc;
		this->transplant(_x, _x->lc);
    }
    else
    {
    	y = this->min(_x->rc);
    	original_color_y = y->color;
    	x = y->rc;
//    	if (y->parent == _x)
//    	    x->parent = y;
//    	else
		if (y->parent != _x)
    	{
    	    this->transplant(y, y->rc);
    	    y->rc = _x->rc;
    	    y->rc->parent = y;
    	}
    	this->transplant(_x, y);
    	y->lc = _x->lc;
    	y->lc->parent = y;
    	y->color = _x->color;
    }
    if (original_color_y == BLACK)
     	while (x != this->root && x->color == BLACK)
     	{ 
    	    if (x == x->parent->lc)
    	    {
    			Node<T>* w = x->parent->rc;
    			if (w->color == RED)
    			{
    		   		w->color = BLACK;
    		    	x->parent->color = RED;
    		    	this->LeftRotate(x->parent);
    		    	w = x->parent->rc;
    			}
    			if (w->lc->color == BLACK && w->rc->color == BLACK)
    			{
    		    	w->color = RED;
    		    	x = x->parent;
    			}
    			else
				{
		    		if (w->rc->color == BLACK)
		    		{
						w->lc->color = BLACK;
						w->color = RED;
						this->RightRotate(w);
						w = x->parent->rc;
		    		}
		    		w->color = x->parent->color;
		    		x->parent->color = BLACK;
		   			w->rc->color = BLACK;
		    		this->LeftRotate(x->parent);
		    // If job finished, but x is not root, set to root
		    // for quitting.
		    		x = this->root;
				}
	    	}
	    	else
     		{
    			Node<T>* w = x->parent->lc;
    			if (w->color == RED)
    			{
    		    	w->color = BLACK;
    		    	x->parent->color = RED;
    		    	this->RightRotate(x->parent);
    		    	w = x->parent->lc;
    			}
    			if (w->rc->color == BLACK && w->lc->color == BLACK)
    			{
    		    	w->color = RED;
    		    	x = x->parent;
    			}
    			else
				{
		    		if (w->lc->color == BLACK)
		    		{
						w->rc->color = BLACK;
						w->color = RED;
						this->LeftRotate(w);
						w = x->parent->lc;
		    		}
		   			w->color = x->parent->color;
		    		x->parent->color = BLACK;
		    		w->lc->color = BLACK;
		    		this->RightRotate(x->parent);
		    // If job finished, but x is not root, set to root
		    // for quitting.
		    		x = this->root;
				}
     		}
     	} 
    x->color = BLACK;
    delete _x;    
};


int main(int argc, char* argv[])
{
    RedBlackTree<double> A(8.0);
    A.insert(5.0);
	A.insert(10.0);
	A.insert(6.5);
	A.insert(4.0);
	A.insert(9.0);
	A.insert(11.0);
	A.insert(3.0);
	A.insert(3.5);
	A.inorder_walk();
	std::cout<<std::endl;
	//RedBlackTree<double> B(8.0);
    //B.insert(5.0);
	//B.insert(10.0);
	//B.insert(6.5);
	//B.insert(5.5);
	//B.insert(9.0);
	//B.insert(11.0);
	//B.insert(3.0);
    //B.inorder_walk();
    A.Delete(6.5);
    A.inorder_walk();
    //A.test_successor(A.tree_search(2));
    //A.test_predecessor(A.tree_search(3));
    //A.test_min();
    //A.test_max();
    //{
    //	std::cout<<A.tree_search(7)<<std::endl;
	//	A.~BinaryTree<int>();
	//	std::cout<<A.tree_search(7)<<std::endl;
	//}
	//std::vector<int> B(6);
	//B[0] = 4;
	//B[1] = 7;
	//B[2] = 3;
	//B[3] = 9;
	//B[4] = 5;
	//B[5] = 6;
	//BinaryTree<int> C;
 	//C.sort(B); 
    return 0;
};
